package tree;


/**
 * Created with IntelliJ IDEA.
 * Description: 106. 从中序与后序遍历序列构造二叉树
 * User: Li_yizYa
 * Date: 2025/6/4
 * Time: 21:56
 */
public class Solution23 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0 ||
            postorder == null || postorder.length == 0) {
            return null;
        }
        return traversal(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode traversal(int[] inorder, int inorderStart, int inorderEnd,
                               int[] postorder, int postorderStart, int postorderEnd) {
        if (postorderStart == postorderEnd) {
            return null;
        }
        // 取后序数组最后一个结点作为根
        int rootVal = postorder[postorderEnd - 1];
        TreeNode root = new TreeNode(rootVal);

        // 根据根分割中序数组
        int midIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootVal) {
                midIndex = i;
                break;
            }
        }
        int leftInorderStart = inorderStart;
        int leftInorderEnd = midIndex;
        int rightInorderStart = midIndex + 1;
        int rightInorderEnd = inorderEnd;

        //分割后序数组
        int leftPostorderStart = postorderStart;
        int leftPostorderEnd = postorderStart + (midIndex - inorderStart);
        int rightPostorderStart = leftPostorderEnd;
        int rightPostorderEnd = postorderEnd - 1;

        root.left = traversal(inorder, leftInorderStart, leftInorderEnd,
                postorder, leftPostorderStart, leftPostorderEnd);
        root.right = traversal(inorder, rightInorderStart, rightInorderEnd,
                postorder, rightPostorderStart, rightPostorderEnd);
        return root;
    }
}
